#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : CreateMaximumNumber.py
# @Time    : 2020/12/2 10:23
# @Description:
from typing import List


class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        """
        Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of
        length k <= m + n from digits of the two. The relative order of the digits from the same array must be
        preserved. Return an array of the k digits.

        Note: You should try to optimize your time and space complexity.

        Example 1:
            Input:
                nums1 = [3, 4, 6, 5]
                nums2 = [9, 1, 2, 5, 8, 3]
                k = 5
            Output:
                [9, 8, 6, 5, 3]
        Example 2:
            Input:
                nums1 = [6, 7]
                nums2 = [6, 0, 4]
                k = 5
            Output:
                [6, 7, 6, 0, 4]
        Example 3:
            Input:
                nums1 = [3, 9]
                nums2 = [8, 9]
                k = 3
            Output:
                [9, 8, 9]

        :param nums1:
        :param nums2:
        :param k:
        :return:
        """
        m, n = len(nums1), len(nums2)
        max_seq = [0] * k
        start, end = max(0, k - n), min(k, m)

        for i in range(start, end + 1):
            subseq1 = self.getMaxSubsequence(nums1, i)
            subseq2 = self.getMaxSubsequence(nums2, k - i)
            cur_maxseq = self.merge(subseq1, subseq2)
            if self.compare(cur_maxseq, 0, max_seq, 0) > 0:
                max_seq = cur_maxseq
        return max_seq

    def getMaxSubsequence(self, nums: List[int], k: int):
        stack = [0] * k
        top = -1
        remain = len(nums) - k

        for i, num in enumerate(nums):
            while top >= 0 and stack[top] < num and remain > 0:
                top -= 1
                remain -= 1
            if top < k - 1:
                top += 1
                stack[top] = num
            else:
                remain -= 1
        return stack

    def merge(self, subseq1, subseq2):
        x, y = len(subseq1), len(subseq2)
        if x == 0:
            return subseq2
        if y == 0:
            return subseq1
        mergelen = x + y
        merged = []

        idx1 = idx2 = 0

        for _ in range(mergelen):
            if self.compare(subseq1, idx1, subseq2, idx2) > 0:
                merged.append(subseq1[idx1])
                idx1 += 1
            else:
                merged.append(subseq2[idx2])
                idx2 += 1
        return merged

    def compare(self, subseq1, idx1, subseq2, idx2):
        x, y = len(subseq1), len(subseq2)
        while idx1 < x and idx2 < y:
            dif = subseq1[idx1] - subseq2[idx2]
            if dif != 0:
                return dif
            idx1 += 1
            idx2 += 1
        return (x - idx1) - (y - idx2)


if __name__ == '__main__':
    S = Solution()
    nums1 = [3, 4, 6, 5]
    nums2 = [9, 1, 2, 5, 8, 3]
    k = 5
    print(S.maxNumber(nums1, nums2, k))
    print('done')
